package a09_贪心算法;

/**
 * <p>
 * a23_监控二叉树复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/5/8
 */
public class a23_监控二叉树复习2 {
    //特点：一个摄像头可以覆盖上中下
    //如何更大程度利用这个特点：因此对于叶子节点，我们可以尽量在叶子节点的父节点放置摄像头，才能更大程度利用这个特点

    //因此需要我们从下往上遍历二叉树，“左右中”

    //如何控制每隔两个节点放摄像头，需要我们记录每个节点的状态
    //根据左右节点的状态确定父节点的状态==>状态转移

    //0:无覆盖   1:有摄像头  2:被覆盖

    //细节：遍历到空节点，返回啥，为了让叶子节点的父节点放摄像头，我们空节点
    //如果空节点是有摄像头，那么叶子节点就是被覆盖了，那么叶子节点的父节点就不需要摄像头了
    //如果空节点是无覆盖，那么叶子节点就是摄像头了
    //如果空节点是被覆盖，那么只需要给叶子结点的父节点放摄像头就可以让叶子节点覆盖

    //如何状态转移？
    //左 = 被覆盖 右 = 被覆盖  父 = 无覆盖
    //左右至少一个无覆盖  父 = 有摄像头
    //左右至少一个有摄像头  父 = 被覆盖

    //注意：如果从底往上，如果到根节点如果是无覆盖的情况，其上需要一个摄像头，但没有父了，所以要+1

    public int minCameraCover(TreeNode root) {
        int traversal = traversal(root);
        if(traversal == 0){
            result++;
        }
        return result;
    }

    private int result = 0;

    public int traversal(TreeNode node) {
        if (node == null) {
            return 2;
        }

        int left = traversal(node.left);
        int right = traversal(node.right);

        if(left == 2 && right == 2){
            return 0;
        }else if(left == 0 || right == 0){
            result++;
            return 1;
        }else if(left == 1 || right == 1){
            return 2;
        }else{
            return -1;
        }
    }
}
